2463. Период строки

Дана строка s. Требуется найти минимальную по длине строку t, такую что s представима в виде конкатенации одной или нескольких строк t.

Вход. Единственная строка s (1 ≤ |s| ≤ 5·10⁶), состоящая из букв латинского алфавита.

Выход. Длина искомой строки t.

Пример входа	Пример выхода
abcabcabc	3

РЕШЕНИЕ

строки – префикс-функция

Анализ алгоритма

Рассмотрим слово S длиной len, являющееся повторением слова T n раз. То есть S = Tⁿ. Пусть длина слова T равна k, причем оно само не является повторением никакого слова.

Построим префикс-функцию p слова S. Поскольку индексы строки начинаются с нуля, то подстрока S[k ...2k – 1] является копией S[0 ...k – 1] и соответственно p[k] = 1, p[k + 1] = 2, …, p[2k – 1] = k. Третий повтор слова T находится в позициях S[2k ...3k – 1] и при этом p[2k] = k + 1, p[2k + 1] = k + 2, …, p[3k – 1] = 2k. Последняя ячейка префикс-функции p[nk – 1] равна (n – 1)k.

Вычислим разницу: len – p[len – 1] = nk – (n – 1)k = k, что равно длине слова T. При этом если len не делится на k, то S не является повторением никакого слова и следует положить k = len.

Реализация алгоритма

В векторе p строим префикс-функцию строки s.

vector<int> p;

char s[5000010];

Функция MaxBorderArray строит префикс-функцию строки s.

vector<int> MaxBorderArray(char *s)

{

int i, j;

vector<int> p(len,0);

p[0] = 0;

for(i = 1; i < len; i++)

{

j = p[i - 1];

while ((j > 0) && (s[i] != s[j])) j = p[j - 1];

if (s[i] == s[j]) p[i] = j + 1; else p[i] = 0;

}

return p;

}

Основная часть программы. Читаем входную строку s, вычисляем ее длину len. Вычисляем в массиве p префикс-функцию.

gets(s); len = strlen(s);

p = MaxBorderArray(s);

Вычисляем разницу между длиной слова и длиной самого длинного префикса строки s, совпадающей с ее суффиксом.

k = len - p[len-1];

Если длина слова len делится на полученную разницу k, то длина искомой строки t равна k. Иначе входная строка s не является степенью никакой строки, поэтому следует положить k равным len.

if (len % k) k = len;

printf("%d\n",k);